The invention relates to Field Programmable Gate Arrays (FPGAs). More particularly, the invention relates to methods for constraining circuit element positions in structured FPGA layouts.
Programmable ICs are a well-known type of digital integrated circuit that may be programmed by a user to perform specified logic functions. One type of programmable IC, the field programmable gate array (FPGA), typically includes an array of configurable logic blocks (CLBs) surrounded by a ring of programmable input/output blocks (IOBs). The CLBs and IOBs are interconnected by a programmable interconnect structure. The CLBs, IOBs, and interconnect structure are typically programmed by loading a stream of configuration data (bitstream) into internal configuration memory cells that define how the CLBs, IOBs, and interconnect structure are configured. The configuration data may be read from memory (e.g., an external PROM) or written into the FPGA by an external device. The collective states of the individual memory cells then determine the function of the FPGA.
One type of FPGA, the Xilinx XC4000(trademark) Series FPGA, is described in detail in pages 4-5 through 4-69 of the Xilinx 1998 Data Book entitled xe2x80x9cThe Programmable Logic Data Book 1998xe2x80x9d, published in 1998 and available from Xilinx, Inc., 2100 Logic Drive, San Jose, Calif. 95124. (Xilinx, Inc., owner of the copyright, has no objection to copying these and other pages referenced herein but otherwise reserves all copyright rights whatsoever.)
FIG. 1A shows a simplified diagram of an XC4000-Series FPGA 100. The FPGA includes a uniform array of CLBs surrounded by a ring of IOBs, as described above. (The exemplary arrays herein are shown smaller than actual logic arrays in order to facilitate clear and simple drawings, but actual logic arrays typically include many more rows and columns of elements.) The CLB array typically includes variations in routing, for example at the outer edges and/or the center of the array, but the CLB array is considered uniform for purposes of this discussion because all of the logic blocks are similar. Each CLB includes two 4-input function generators, one 3-input function generator, and two flip-flops, in addition to other logic.
A more advanced FPGA is the Xilinx Virtex(copyright) FPGA, which in addition to the CLBs includes blocks of Random Access Memory (RAM). The Xilinx Virtex-II FPGA is described in detail in pages 3-75 through 3-96 of the Xilinx 2000 Data Book entitled xe2x80x9cThe Programmable Logic Data Book 2000xe2x80x9d, published April, 2000, available from Xilinx, Inc., 2100 Logic Drive, San Jose, Calif. 95124.
FIG. 1B shows a simplified diagram of a Virtex FPGA 110. The FPGA includes a uniform array of CLBs, flanked by two columns of RAM blocks, with a ring of IOBs around the CLBs and RAM blocks. The Virtex CLB is organized into two functionally similar blocks called xe2x80x9cslicesxe2x80x9d, each of which includes two 4-input function generators and two flip-flops, in addition to other logic. The RAM blocks, of course, include different elements and are larger than the CLBs.
An even more advanced FPGA is the Xilinx Virtex(copyright)-II FPGA, which in addition to the CLBs includes blocks of Random Access Memory (RAM) and blocks implementing multiplier functions. (The Xilinx Virtex-II FPGA is described in detail in pages 33-75 of the xe2x80x9cVirtex-II Platform FPGA Handbookxe2x80x9d, published January, 2001, available from Xilinx, Inc., 2100 Logic Drive, San Jose, Calif. 95124.) The RAM and multiplier blocks are interspersed within the CLB array, forming a non-uniform array of logic blocks, as shown in FIG. 1C.
FIG. 1C shows a simplified diagram of a Virtex-II FPGA 120. The FPGA includes an array of CLBS, with columns of RAM blocks and multiplier blocks inserted within the CLB array. The resulting logic array is therefore non-uniform in nature, including three different kinds of logic blocks. The logic array is surrounded by a ring of IOBs, the IOB ring also including Digital Clock Manager (DCM) logic blocks. The Virtex-II FPGA also includes other types of logic blocks, but these are omitted from FIG. 1C for the sake of clarity. The Virtex-II CLB is organized into four slices, each of which includes two 4-input function generators and two flip-flops, in addition to other logic. Each CLB also includes two tristate buffers. The RAM blocks and multiplier blocks include different elements from the CLBs. The RAM and multiplier blocks are designed such that the height of each block is a multiple of the CLB height.
As FPGA designs increase in complexity, they reach a point at which the designer cannot deal with the entire design at the gate level. Where once a typical FPGA design comprised perhaps 5,000 gates, FPGA-designs with over 100,000 gates are now common. To deal with this complexity, circuits are typically partitioned into smaller circuits that are more easily handled. Often, these smaller circuits are divided into yet smaller circuits, imposing on the design a multi-level hierarchy of logical blocks.
Libraries of predeveloped blocks of logic have been developed that can be included in an FPGA design. Such library modules include, for example, adders, multipliers, filters, and other arithmetic and DSP functions from which complex designs can be readily constructed. The use of predeveloped logic blocks permits faster design cycles, by eliminating the redesign of duplicated circuits. Further, such blocks are typically well tested, thereby making it easier to develop a reliable complex design.
To offer the best possible performance, some library modules have a fixed size and shape, with relative location restrictions on each element. One type of module having a fixed size and shape is the Relationally Placed Macro (RPM) from Xilinx, Inc. RPMs are described in pages 4-96 and 4-97 of the xe2x80x9cLibraries Guidexe2x80x9d (hereinafter referred to as the xe2x80x9cXilinx Libraries Guidexe2x80x9d), published October 1995 and available from Xilinx, Inc. An RPM is a schematic that includes constraints defining the order and structure of the underlying circuits. The location of each element within the RPM is defined relative to other elements in the RPM, regardless of the eventual placement of the RPM in the overall design. For example, an RPM might contain 8 flip-flops constrained to be placed into four XC4000 CLBs in a vertical column. The column of four CLBs can then be placed anywhere in any XC4000 Series FPGA.
Relative CLB locations in an RPM are specified using a Relative Location constraint called xe2x80x9cRLOCxe2x80x9d. RLOC constraints are described in detail in pages 4-71 through 4-95 of the Xilinx Libraries Guide. FIG. 2A shows how RLOC constraints are related to physical location in an array of XC4000 Series logic blocks, and how they are associated with assigned coordinates. Elements having an RLOC value of R0C0 are located in a given CLB corresponding to the (0,0) coordinate location. The next CLB xe2x80x9cbelowxe2x80x9d the (0,0) CLB is designated as R1C0, corresponding to the (0,1) coordinate location. When the FPGA design is mapped and placed by the FPGA implementation tools (prior to the final routing step), these RLOC constraints are referenced and, in effect, make the RPM a xe2x80x9cjigsaw puzzle piecexe2x80x9d to be fitted into the FPGA along with other elements and/or modules. Although the RPM has a rigid size and shape, other logic can be placed within the borders of the RPM.
Logic can also be mapped to elements within the logic block. For example, the function generators and flip-flops inside a CLB can be directly addressed using RLOC constraints. For example, in an XC4000 Series FPGA, the xe2x80x9cFxe2x80x9d function generator within the (0,0) CLB is addressed by assigning the constraint xe2x80x9cRLOC=R0C0.Fxe2x80x9d to the logic element assigned to that location. The xe2x80x9cYxe2x80x9d flip-flop in the same CLB is addressed by assigning the constraint xe2x80x9cRLOC=R0C0.FFYxe2x80x9d, and so forth.
Some users, such as those requiring the maximum possible performance, the smallest possible implementation, or an exact pinout, want to specify exact locations for their circuit elements, rather than relative locations. To specify an exact location, the xe2x80x9cLOCxe2x80x9d attribute is used. The LOC attribute is similar to the RLOC attribute except that the implementation software always places the constrained element in the exact location specified. Other location constraints are also typically supported. For example, the Xilinx FPGA implementation tools support, in addition to the RLOC and LOC attributes, the location attributes U_SET, H_SET, and so forth. However, the RLOC attribute is used herein as an exemplary location constraint.
FIG. 2A shows a uniform CLB array 200, such as those in an XC4000 Series FPGA. Each CLB in the array has a unique set of coordinates, e.g., (0,0) for the CLB in the upper left corner. To place a circuit element into a particular CLB, an RLOC attribute is attached to the element, referencing the coordinates of the target CLB. For example, attaching the constraint xe2x80x9cRLOC=R0C0xe2x80x9d tells the FPGA implementation tools to place the element into the CLB at coordinates (0,0) in the upper left corner of the array.
FIG. 2B shows an array 210 of logic blocks in a Virtex FPGA. (The numbers and relative sizes of CLBs and RAM blocks in the figures herein are not representative of actual Virtex and Virtex-II FPGAs.) A centrally-located array of CLBs uses the same coordinate system as the array of FIG. 2A. The flanking columns of RAM blocks use a similar coordinate system separate from the coordinate system of the CLBs. For example, the RAM block closest to the upper left corner of the array has the coordinates (0,0). This duplication of coordinates can lead to a duplication of RLOC constraints, with both the upper left CLB and the upper left RAM block being specified by attaching the constraint xe2x80x9cRLOC=R0C0xe2x80x9d. However, each circuit element from a library of available elements implies a particular type of logic block, so the FPGA implementation tools are able to correctly target the circuit elements to the intended locations. Another solution to this duplication problem is to require the location constraint to include information as to the type of the destination logic block, e.g., xe2x80x9cRLOC=RAMB4_R0C0xe2x80x9d.
FIG. 2C shows how this method of specifying locations can be extended to the Virtex-II FPGA, which includes three types of logic blocks in the logic array. Using the previously-described method of designating relative locations, each type of logic block has a separate coordinate system, as shown in FIG. 2C. The situation is further complicated if the logic array is defined to include the ring of IOBs shown in FIG. 1C, which also includes the Digital Clock Manager (DOM) blocks and other types of blocks not shown in FIG. 1C. As can be seen from this example, methods for specifying locations in non-uniform arrays can be quite complex. It is desirable to provide a method of specifying locations that is simple and straightforward and can be used with any coordinate system applied to both uniform and non-uniform arrays.
The above-described methods for specifying circuit element positions are generally directed to low-level constraints, such as specifying a particular logic block (e.g., a particular CLB or RAM block) as a destination for the constrained circuit element. There are some known methods for constraining elements at a higher level. For example, the location constraint xe2x80x9cLOC=TLxe2x80x9d attached to a decode circuit element in an XC4000 Series device constrains the element to be placed in the left half of the top edge of the FPGA, as described on pages 4-69 and 4-70 of the Xilinx Libraries Guide. Although this type of constraint is at a higher level than those previously described, these methods are still limited to a single level of hierarchy.
FPGA users often wish to implement designs too large for a single FPGA. Such a user might want to specify a particular FPGA on which a circuit element is to be placed, while also specifying a particular logic block in the target FPGA as the target destination. It is therefore desirable to provide methods for specifying circuit element positions that can be extended to multiple levels of a design hierarchy, e.g., including that of multiple FPGAs.
The invention provides methods for designating desired locations for circuit elements to be implemented in a target programmable system such as a Field Programmable Gate Array (FPGA). Location information applied to a circuit element can include hierarchical information about two or more levels of physical partitioning. According to a first aspect of the invention, a target FPGA or system is divided into blocks at various levels of hierarchy. Each block within the same higher-level block has a different identifier. A user can specify a desired location for a circuit element at any or all of these levels of hierarchy. Location information can include references to two or more of these levels, or to two or more different blocks at the same hierarchical level.
For example, a system (Level 0) can include two FPGAs, each at Level 1. Each block at Level 1 (e.g., each of the two FPGAs) must have a different identifier than each other block at Level 1. At the next level of hierarchy (Level 2), each FPGA can include an array of CLBS, an array of RAM and multiplier blocks, and an array of processor blocks. Each block at Level 2 (e.g., each CLB array, RAM/multiplier array, and processor array) has a different identifier from all of the other blocks in the same Level 1 block. Each of these blocks in turn can include other blocks (Level 3), uniquely identified within their Level 2 block. A user can specify a desired location for a circuit element at two or more levels of hierarchy, or in two different ways at the same level of hierarchy. The number of possible levels of hierarchy is limited only by the capability of the computer and software used to specify the circuit and implement the circuit in the target FPGA or system.
Preferably, a desired location is specified using a single location constraint set to a value comprising a string of identifiers separated by delimiters. Not every level need be specified. For example, a user can specify that a given circuit element be placed in a certain FPGA, without specifying a location within the FPGA. Similarly, a location within an FPGA can be specified without specifying which FPGA is to be used. A particular slice within a CLB can be specified, or the exact placement within the CLB can be left up to the implementation software. Other levels of hierarchy can be skipped or specified, as desired. In order to skip a level of hierarchy, a xe2x80x9cplaceholderxe2x80x9d can be inserted into the text string. For example, an asterisk can be used to indicate a match to all identifiers at a given level of hierarchy. Other known methods of performing a regular expression match can also be used.
In one embodiment, a given logic block can belong to more than one larger block at a given level of hierarchy. For example, a CLB in an array of CLBs can be addressed by specifying a row of CLBs, or by specifying a column of CLBs. Where a logic block belongs to more than one larger block at the same level, two identifiers at the same level can be specified. In one embodiment, when two areas at the same level are specified, the placement is limited to an overlapping area shared by the two identified areas of the target programmable system. As long as the implementation software recognizes the identifiers used to designate the blocks at any given level of hierarchy, the identifiers can be used to specify a location constraint.
According to a second aspect of the invention, a uniform coordinate system is applied to all blocks at a given level, even in a non-uniform array. In one embodiment, a non-uniform array of logic blocks is divided into tiles of uniform size and shape, and a uniform coordinate system is applied to the tiles. Thus, any tile in the array can be addressed using a uniform coordinate system, regardless of the size, shape, or nature of the logic block or blocks comprising the tile. In another embodiment, the tiles are of uniform height but varying widths, or of uniform width but varying height. The uniform-coordinate system can still be applied. This aspect of the invention can also be applied to a system having only a single level of hierarchy.